package org.example.binaryTree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Code01_PreInPosTraversal {


    //先序
    public static void preOrderUnRecur(Node head) {
        if(head != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(head);
            while (!stack.empty()) {
                head = stack.pop();
                System.out.println(head.value);
                if(head.right != null) {
                    stack.push(head.right);
                }
                if(head.left != null) {
                    stack.push(head.left);
                }
            }
        }
    }

    public static void inOrderUnRecur(Node head) {
        if(head != null) {
            Stack<Node> stack1 = new Stack<>();
            while (!stack1.empty() || head != null) {
                if(head != null) {
                    stack1.push(head);
                    head = head.left;
                } else {
                    head = stack1.pop();
                    System.out.println(head.value);
                    head = head.right;
                }


            }

        }
    }
    public static void posOrderUnRecur(Node head) {
        if(head != null) {
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();

            stack1.add(head);
            while (!stack1.empty()) {
                head = stack1.pop();
                stack2.push(head);
                if(head.left != null) {
                    stack1.push(head.left);
                }
                if(head.right != null) {
                    stack1.push(head.right);
                }


            }
            while (!stack2.empty()) {
                System.out.println(stack2.pop().value);
            }
        }
    }

    //宽度优先遍历
    public static int wigthOrder(Node head) {
       if(head == null) {
           return 0;
       }
       Queue<Node> queue = new LinkedList();
       queue.add(head);
        HashMap<Node,Integer> levelMap = new HashMap<>();
        levelMap.put(head,1);
        //表示node所在的层数
        int curLevel = 1;
        //每一层的node数
        int curLevelNodes = 0;
        //每层最大node数
        int max = Integer.MIN_VALUE;
       while (!queue.isEmpty()) {
           Node cur = queue.poll();
           int curNodeLevel = levelMap.get(cur);
           if(curNodeLevel == curLevel) {
               curLevelNodes++;
               max = Math.max(max,curLevelNodes);
           }else {
               //max = Math.max(max,curLevelNodes);
               curLevel++;
               //每一级 刚单出的node
               curLevelNodes = 1;
           }

           //System.out.println(cur.value);
           if(cur.left !=null) {
               levelMap.put(cur.left,curNodeLevel+1);
               queue.add(cur.left);
           }
           if(cur.right != null) {
               levelMap.put(cur.right,curNodeLevel+1);
               queue.add(cur.right);
           }
       }
       return max;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node1.left = node2;
        node1.right = node3;
        node2.right = node4;
        //node2.left = null;
        node3.left = node5;
        //node3.right = null;
        node4.left= node6;
        node4.right = node7;
        node5.left= node8;
        node5.right = node9;
        System.out.println(wigthOrder(node1));

    }
}
